Nowadays, one-dimensional and two-dimensional bar codes are ubiquitous in the form of so-called “tags”. Specifically, such bar codes can be found on consumer products, electronic and non-electronic devices, machines, vehicles, and also on documents, such as tickets, papers, currency bills etc. Besides the one-dimensional bar code also the two-dimensional bar code has gained in significance during recent years. Whereas the one-dimensional barcode is classically limited to encoding information only in one linear dimension, the two-dimensional bar code, comprising at least first and second type elements arranged in an ordered grid, allows for substantially increasing amount of data amount that can be encoded.
FIGS. 1A and 1B show schematic views of conventional two-dimensional bar codes that encode information by means of arranging at least first and second type elements, such as rectangles, dots, triangles and the like, for encoding information. At least two distinguishable types of elements are used for encoding information in form of binary units, i.e. bits. For example, a white-printed square as a first type element may represent the information “0”, whereas a black-printed square as a second type element represents the information “1”.
FIG. 1A shows a schematic view of a two-dimensional bar code according to the GS1 (Trademark) DataMatrix ECC 200 standard (GS1 being an international association providing standards for two-dimensional barcodes). This two-dimensional bar code comprises two main areas, namely the so-called “finder pattern” 10 and the data 20. The latter data 20 carries the actual payload data of the bar code and comprises first and second type elements 21, 22 arranged in an ordered grid. The finder pattern 10 is also composed of the first and second type elements, and is, in turn, divided into the so-called “L finder pattern” 11 (also called L-shape solid line, L-line, solid line, etc.) and the so-called “clock track” 12 (also called clock line, L-shape clock line etc.).
According to a convention, the clock line 12 is formed by linearly alternating the arrangement of first and second type elements 21, 22. Therefore, the clock line 12 provides transitions between said first and second type elements 21, 22, whereas the solid line 11 does not. Both segments (or legs) of both the solid line 11 and the clock line 12 intersect at a corner in a substantially perpendicular fashion. Thus, a rectangle-like outline of the two-dimensional barcode is formed by the solid line 11 and the clock line 12.
According to another convention, the intersecting element of the two segments of the clock line 12 is of a pre-determined type, namely either the first type 21 or the second type 22. Specifically, a current convention defines this intersection element 13 as a light element, for example in the context of the present disclosure a first type element, as opposed to dark elements, for example in the context of the present disclosure a second type element.
Whereas FIG. 1A shows a square version of the DataMatrix bar code 1, the current conventions are not limited to square like bar codes and FIG. 1B shows an example of a rectangle implementation 1′. Again, the two-dimensional bar code is delimited by an outline comprising an L-shape solid line 11′ and an L-shape clock line 12′. However, since the general outline is not limited to squares, one segment 111′ of the solid line 11′ may be shorter than the other segment 112′ of the solid line 11′. Correspondingly, one segment 121′ of the clock line 12′ can be shorter than the other segment 122′.
Generally, the first and second type elements 21, 22 may take any distinguishable form. This aspect is depicted in FIG. 2A that shows the first type element 21 as a general right-hatched square/rectangle and the second type element as a general left-hatched square/rectangle 22. This generalization comes from the fact that a two-dimensional bar code is not necessarily printed by using, for example, a black dye on white paper. Rather, the two-dimensional bar code can be well implemented also by means of color dyes or inks; thermo printing on heat-sensitive paper; mechanical means, such as milling, embossing, grinding, etc.; or physical/chemical means, such as laser etching, acid etching, etc. Any type of implementation is possible as long as the elements can be distinguished into their respective type in, for example, digital image data that has been obtained from the two-dimensional bar code being. For example, a digital camera can obtain digital image data of two-dimensional bar code that is printed on a paper document or laser-etched on a metal can.
Further, the various printing techniques may also result in different “qualities” of a two-dimensional bar code. Besides the somewhat optimal representation (as shown for example in FIGS. 1A and 1B), also implementations with individual elements are possible, such as shown in conjunction with FIG. 2B. There, even the solid line 11 has interruptions between two adjacent elements of the same type 22. However, the average width of such interruptions may still ensure the characteristics of no transition in element type between adjacent elements as shown with reference numeral 28. On the other hand, a transition between the element type can be still identified by means of the characteristic width of the interruption as shown by reference numeral 29.
FIG. 2C shows a somewhat opposite situation in which even diagonally adjacent elements merge. However, also in this case it is assumed that the first and second type elements can be distinguished and that their respective association to positions in an ordered grid is still possible.
The decoding of a two-dimensional bar code usually begins with taking a photographic image of the two-dimensional barcode on a given item, such as a consumer product or document. This image is then obtained as digital image data defining respective pixel values for the pixels of the image. This digital image data is then subject to image processing by means of a processing unit (e.g., CPU, computer, server, embedded system, ASIC, etc.). Such processing may be divided into various individual steps for eventually decoding the data that is encoded in the two-dimensional bar code.
Since the image of the two-dimensional bar code is usually taken with an arbitrary perspective, meaning that the precise distance, angle, and general orientation of the imaging device (e.g. a CCD camera) relative to the two-dimensional bar code is unknown. Therefore, it may be necessary to first identify the image or area of the two-dimensional bar code within given digital image data. Once the two-dimensional barcode has been identified in the digital image data, processing may proceed to identifying and decoding the individual elements of the bar code data.
The initial steps of image processing may thus include the determination of so-called approximate corners of the two-dimensional bar code within given digital image data. Then the four segments connecting these four approximate corners to a rectangle, or—more generally—a 4-polygon, can be scanned for determining the length in individual pixels and/or elements and for counting the transition between first and second type elements.
A conventional method involves for the above purpose eight scanning operations in which each of the four segments is first scanned to determine the length in terms of pixels and/or elements and then scanned for counting transitions between the first and second type elements along this segment. Having this information at hand, the long and short segments of the solid line as well as the long and short segments of the clock line can be identified. The same applies for square implementations of the two-dimensional bar code in that the two segments of the clock line and the solid line have identical length, at least in terms of elements. The processing may then proceed to identifying the pay load data since the structure of the grid and the relative position of each identified element within this grid can be obtained.
Since use of two-dimensional bar codes becomes more and more common, also the requirements on identifying and/or decoding two-dimensional bar codes become more and more demanding. Specifically, it may be required to identify and/or decode a two-dimensional bar code fast and, nevertheless, in a reliable fashion. For example, two-dimensional bar codes may be used in production lines where a large number of individual items, such as consumer products (e.g., food packages, metal cans, electronic devices, etc.), have to be identified within a short period of time. A specific example could be a filling line of beverage cans, in which the individual cans pass by a certain observation point with high speed so that only a few milliseconds may be available to identify one individual can. Therefore, a two-dimensional bar code being applied to the individual item needs to be identified and decoded within only a couple of milliseconds or less.
Therefore, there is a demand for improving the time efficiency of existing identification and decoding schemes so that the overall time required from taking an image of two-dimensional bar codes to eventually obtaining the decoded pay load data of the two-dimensional bar code can be minimized. At the same time, however, the improved method shall also provide reliability in terms of correct identification and/or decoding of the two-dimensional bar code.